﻿#pragma once
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <algorithm>
#include "tree.h"

using namespace std;

namespace LeetCode
{
	namespace SlotArray
	{
		//冒泡排序
		void SlotVecotr1(vector<int>& vec)
		{
			for (int i = vec.size() - 1; i >= 0; --i)
			{
				for (int j = 0; j < i; ++j)
				{
					if (vec.at(i) < vec.at(j))
					{
						int temp = vec.at(i);
						vec.at(i) = vec.at(j);
						vec.at(j) = temp;
					}
				}
			}
		}
	}
	
	namespace Find {
		//二分查找
		int Find2(vector<int>& nums, int target)
		{
			int l = 0, r = nums.size() - 1;
			while (l <= r)
			{
				int mid = l + (r - l) / 2;
				if (target == nums.at(mid))
					return mid;

				if (target > nums.at(mid))
					l = mid + 1;
				else
					r = mid - 1;
			}


			return -1;
		}
	}

	/*
	struct ListNode {
		int val;
		ListNode* next;
		ListNode() : val(0), next(nullptr) {}
		ListNode(int x) : val(x), next(nullptr) {}
		ListNode(int x, ListNode* next) : val(x), next(next) {}
	};

	string convert(string s, int numRows)
	{
		string strRet;
		int step = numRows * 2 - 2;
		int round = ceil((float)s.length() / (float)step);
		for (int i = 0; i <= step / 2; ++i)
		{
			for (int j = 0; j < round; ++j)
			{
				int pos = step * j + i;
				strRet += s[pos];
				if (pos % step != 0 && pos % (step / 2) != 0)
				{
					pos = (j + 1) * step - pos % step;
					if (pos < s.length())
						strRet += s[pos];
				}
			}

		}

		return strRet;
	}

	//7. 整数反转
	//给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围[−231, 231 − 1] ，就返回 0
	int reverse(int x) {
		int MAX = pow(2, 31) - 1;
		int MIN = pow(-2, 31);
		int ret = 0;
		while (x != 0)
		{
			int mode = x % 10;
			if (x > 0 && ret > ((MAX - mode) / 10))
				return 0;
			else if (x < 0 && ret < ((MIN - mode) / 10))
				return 0;
			else
				ret = ret * 10 + x % 10;
			x = x / 10;
		}

		return ret;
	}

	//8. 字符串转换整数(atoi)
	int myAtoi(string s) {
		unsigned int MIN = pow(-2, 31);
		unsigned int MAX = pow(2, 31)-1;
		int ret = 0;
		int ss = 0;
		bool begin = false;
		for (int i = 0; i < s.length(); ++i)
		{
			if (!begin)
			{
				if (s[i] == ' ')
					continue;
				else if (s[i] == '+' || s[i] == '-')
				{
					begin = true;
					if (s[i] == '+')
						ss = 1;
					else
						ss = -1;
				}
				else if (s[i] >= '0' && s[i] <= '9')
				{
					ss = 1;
					begin = true;
					--i;
				}
				else
					break;
			}
			else
			{
				if (s[i] < '0' || s[i] > '9')
					break;
				else
				{
					int temp = (s[i] - 0x30) * ss;
					if (ret == 0)
					{
						if (s[i] != '0')
							ret = temp;
					}
					else
					{
						if (ret < 0 && ret < (MIN - temp) / 10)
							return MIN;
						else if (ret > 0 && ret > (MAX - temp) / 10)
							return MAX;
						else
						{
							ret = ret * 10 + temp;
						}
					}
				}

			}
		}

		return ret;

	}

	//9. 回文数
	bool isPalindrome(int x) {
		if (x < 0)
			return false;

		vector<int> vec;
		while (x > 0)
		{
			vec.push_back(x % 10);
			x = x / 10;
		}

		int i = 0, j = vec.size() - 1;
		while (i < j)
		{
			if (vec.at(i) != vec.at(j))
				return false;
			++i;
			--j;
		}

		return true;
	}

	//12. 整数转罗马数字
	string intToRoman(int num) {
		string ret;
		while (num > 0)
		{
			if (num >= 1000)
			{
				ret += "M";
				num -= 1000;
			}
			else if (num >= 900)
			{
				ret += "CM";
				num -= 900;
			}
			else if (num >= 500)
			{
				ret += "D";
				num -= 500;
			}
			else if (num >= 400)
			{
				ret += "CD";
				num -= 400;
			}
			else if (num >= 100)
			{
				ret += "C";
				num -= 100;
			}
			else if (num >= 90)
			{
				ret += "XC";
				num -= 90;
			}
			else if (num >= 50)
			{
				ret += "L";
				num -= 50;
			}
			else if (num >= 40)
			{
				ret += "XL";
				num -= 40;
			}
			else if (num >= 10)
			{
				ret += "X";
				num -= 10;
			}
			else if (num >= 9)
			{
				ret += "IX";
				num -= 10;
			}
			else if (num >= 5)
			{
				ret += "V";
				num -= 5;
			}
			else if (num >= 4)
			{
				ret += "IV";
				num -= 4;
			}
			else if (num >= 1)
			{
				ret += "I";
				num -= 1;
			}
		}
		

		return ret;
	}

	//13. 罗马数字转整数
	int romanToInt(string s)
	{
		int ret = 0;
		for (int i = 0; i < s.length(); ++i)
		{
			if (s[i] == 'I')
			{
				if (s[i + 1] == 'V')
				{
					ret += 4;
					++i;
				}
				else if (s[i + 1] == 'X')
				{
					ret += 9;
					++i;
				}
				else
					ret += 1;
			}
			else if (s[i] == 'V')
			{
				ret += 5;
			}
			else if (s[i] == 'X')
			{
				if (s[i + 1] == 'L')
				{
					ret += 40;
					++i;
				}
				else if (s[i + 1] == 'C')
				{
					ret += 90;
					++i;
				}
				else
					ret += 10;
			}
			else if (s[i] == 'L')
			{
				ret += 50;
			}
			else if (s[i] == 'C')
			{
				if (s[i + 1] == 'D')
				{
					ret += 400;
					++i;
				}
				else if (s[i + 1] == 'M')
				{
					ret += 900;
					++i;
				}
				else
					ret += 100;
			}
			else if (s[i] == 'D')
			{
				ret += 500;
			}
			else if (s[i] == 'M')
			{
				ret += 1000;
			}
		}

		return ret;
	}

	//14. 最长公共前缀
	string longestCommonPrefixSub(string s1, string s2)
	{
		string strRet;
		if (s1.length() == 0 || s2.length() == 0)
			return string();

		int begin = 0, end = -1;
		int len = min(s1.length(), s2.length());
		for (int i = 0; i < len; ++i)
		{
			if (s1[i] != s2[i])
			{
				break;
			}
			end = i;
		}

		if (end < begin)
			return string();
		
		strRet = s1.substr(begin, end - begin + 1);

		return strRet;
	}

	string longestCommonPrefix(vector<string>& strs) {
		string s1 = strs.at(0);
		for (int i = 1; i < strs.size(); ++i)
		{
			s1 = longestCommonPrefixSub(s1, strs.at(i));
			if (s1.length() == 0)
				return string();
		}

		return s1;

	}

	//15. 三数之和
	vector<vector<int>> threeSum(vector<int>& nums) 
	{
		vector<vector<int>> ret;
		//排序
		//SlotArray::SlotVecotr1(nums);
		sort(nums.begin(), nums.end());

		//三重循环查找
		int lastI = 0, lastJ = 0, lastK = 0;
		for (int i = 0; i < nums.size(); )
		{
			int startPos = i + 1, endPos = nums.size() - 1;
			while (startPos < endPos)
			{
				int iTemp = nums.at(i) + nums.at(startPos) + nums.at(endPos);
				if (iTemp == 0)
				{
					ret.push_back(vector<int>{nums.at(i), nums.at(startPos), nums.at(endPos)});
					
					//移动startPos到下一个非重复值
					int j = startPos + 1;
					while (j < endPos)
					{
						if (nums.at(j) == nums.at(startPos))
							++j;
						else
							break;
					}
					startPos = j;

					//移动startPos到下一个非重复值
					j = endPos - 1;
					while (j > startPos)
					{
						if (nums.at(j) == nums.at(endPos))
							--j;
						else
							break;
					}
					endPos = j;

				}
				else if (iTemp < 0)
				{
					//移动startPos
					int j = startPos + 1;
					while (j < endPos)
					{
						if (nums.at(j) == nums.at(startPos))
							++j;
						else
							break;
					}
					startPos = j;
				}
				else
				{
					//移动endPos
					int j = endPos - 1;
					while (j > startPos)
					{
						if (nums.at(j) == nums.at(endPos))
							--j;
						else
							break;
					}
					endPos = j;
				}
			}

			//移动到下一个非重复原素
			int j = i + 1;
			while (j< nums.size())
			{
				if (nums.at(j) == nums.at(i))
					++j;
				else
					break;
			}
			i = j;
		}

		

		return ret;
	}

	//16. 最接近的三数之和
	int threeSumClosest(vector<int>& nums, int target) {
		
		sort(nums.begin(), nums.end());
		int ret = nums.at(0) + nums.at(1) + nums.at(2);

		//三重循环查找
		for (int i = 0; i < nums.size(); )
		{
			int startPos = i + 1, endPos = nums.size() - 1;
			while (startPos < endPos)
			{
				int iTemp = (nums.at(i) + nums.at(startPos) + nums.at(endPos));
				if (iTemp == target)
				{
					return target;
				}
				else if (iTemp < target)
				{
					if (abs(iTemp - target) < abs(ret - target))
						ret = iTemp;

					//移动startPos
					int j = startPos + 1;
					while (j < endPos)
					{
						if (nums.at(j) == nums.at(startPos))
							++j;
						else
							break;
					}
					startPos = j;
				}
				else
				{
					if (abs(iTemp - target) < abs(ret - target))
						ret = iTemp;

					//移动endPos
					int j = endPos - 1;
					while (j > startPos)
					{
						if (nums.at(j) == nums.at(endPos))
							--j;
						else
							break;
					}
					endPos = j;
				}
			}

			//移动到下一个非重复原素
			int j = i + 1;
			while (j < nums.size())
			{
				if (nums.at(j) == nums.at(i))
					++j;
				else
					break;
			}
			i = j;
		}



		return ret;
	}

	//17. 电话号码的字母组合
	vector<string> letterCombinations(string digits)
	{
		vector<vector<string>> matrix;
		for (int i = 2; i <= 9; ++i)
		{
			vector<string> temp;
			if (i == 2)
				temp = vector<string>{ "a","b","c" };
			else if (i == 3)
				temp = vector<string>{ "d","e","f" };
			else if (i == 4)
				temp = vector<string>{ "g","h","i" };
			else if (i == 5)
				temp = vector<string>{ "j","k","l" };
			else if (i == 6)
				temp = vector<string>{ "m","n","o" };
			else if (i == 7)
				temp = vector<string>{ "p","q","r","s" };
			else if (i == 8)
				temp = vector<string>{ "t","u","v" };
			else if (i == 9)
				temp = vector<string>{ "w","x","y","z" };
			matrix.push_back(temp);
		}

		vector<string> out;
		for (int i = 0; i < digits.size(); ++i)
		{
			int line = (digits[i] - 0x32);
			if (i == 0)
			{
				for (int j = 0; j < matrix.at(line).size(); ++j)
				{
					out.push_back(matrix.at(line).at(j));
				}
			}
			else
			{
				int curSize = out.size();
				for (int i = 0; i < curSize; ++i)
				{
					string ttmp = out.at(i);
					for (int j = 0; j < matrix.at(line).size(); ++j)
					{
						if (j == 0)
							out.at(i) = out.at(i) + matrix.at(line).at(j);
						else
							out.push_back(ttmp + matrix.at(line).at(j));
					}
				}
			}
				
		}
		
		return out;
	}
	
	//18. 四数之和
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
		vector<vector<int>> ret;

		//排序
		sort(nums.begin(), nums.end());

		//四重循环查找
		for (int i = 0; i < nums.size(); )
		{
			for (int j = i+1; j < nums.size();)
			{
				int startPos = j + 1, endPos = nums.size() - 1;
				while (startPos < endPos)
				{
					int iTemp = (long)nums.at(i) + (long)nums.at(j) + (long)nums.at(startPos) + (long)nums.at(endPos);
					if (iTemp == target)
					{
						ret.push_back(vector<int>{nums.at(i), nums.at(j),nums.at(startPos), nums.at(endPos)});

						//移动startPos到下一个非重复值
						int k = startPos + 1;
						while (k < endPos)
						{
							if (nums.at(k) == nums.at(startPos))
								++k;
							else
								break;
						}
						startPos = k;

						//移动startPos到下一个非重复值
						k = endPos - 1;
						while (k > startPos)
						{
							if (nums.at(k) == nums.at(endPos))
								--k;
							else
								break;
						}
						endPos = k;

					}
					else if (iTemp < target)
					{
						//移动startPos
						int k = startPos + 1;
						while (k < endPos)
						{
							if (nums.at(k) == nums.at(startPos))
								++k;
							else
								break;
						}
						startPos = k;
					}
					else
					{
						//移动endPos
						int k = endPos - 1;
						while (k > startPos)
						{
							if (nums.at(k) == nums.at(endPos))
								--k;
							else
								break;
						}
						endPos = k;
					}
				}


				//移动到下一个非重复原素
				int k = j + 1;
				while (k < nums.size())
				{
					if (nums.at(k) == nums.at(j))
						++k;
					else
						break;
				}
				j = k;
			}
			
			//移动到下一个非重复原素
			int k = i + 1;
			while (k < nums.size())
			{
				if (nums.at(k) == nums.at(i))
					++k;
				else
					break;
			}
			i = k;
		}


		return ret;
	}

	//19. 删除链表的倒数第 N 个结点
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		return nullptr;
	}

	//21. 合并两个有序链表
	ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
		if (list1 == nullptr)
			return list2;

		if (list2 == nullptr)
			return list1;

		ListNode* pHead = list1->val < list2->val ? list1 : list2;
		if (pHead == list1)
			list1 = list1->next;
		else
			list2 = list2->next;

		ListNode* pTail = pHead;
		while (list1 != nullptr || list2 != nullptr)
		{
			if (list1 == nullptr)
			{
				pTail->next = list2;
				break;
			}
			else if (list2 == nullptr)
			{
				pTail->next = list1;
				break;
			}
			else
			{
				if (list1->val < list2->val)
				{
					pTail->next = list1;
					list1 = list1->next;
					
				}
				else {
					pTail->next = list2;
					list2 = list2->next;
				}
				pTail = pTail->next;
			}
		}

		return pHead;
	}

	//851. 喧闹和富有
	vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
		int pesron = quiet.size();
		vector<int> ret;
		if (pesron == 1)
		{
			ret.push_back(quiet.at(0));
			return ret;
		}

		vector<vector<int>>  tt;
		//处理金钱关系
		for (int i = 0; i < pesron; ++i)
		{
			int iPush = i;
			vector<int> tempVec;
			tempVec.push_back(i);
			for (int j = 0; j < tempVec.size(); ++j)
			{
				//遍历richer
				for (int k = 0; k < richer.size(); ++k)
				{
					auto ttt = richer.at(k);
					if (richer.at(k).at(1) == tempVec.at(j))
					{
						tempVec.push_back(richer.at(k).at(0));
						if (quiet.at(iPush) > quiet.at(richer.at(k).at(0)))
						{
							iPush = richer.at(k).at(0);
						}
					}
				}
			}

			ret.push_back(iPush);
		}
		return ret;
	}

	//剑指 Offer 31. 栈的压入、弹出序列
	bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
	{
		stack<int> tempVec;
		int pushFlag = 0,popFlag = 0;
		//建立初始状态
		for (;pushFlag < pushed.size(); ++pushFlag)
		{
			if (popped.at(0) != pushed.at(pushFlag))
				tempVec.push(pushed.at(pushFlag));
			else
				break;
		}

		int pushSize =  pushed.size();
		while (pushFlag < pushSize)
		{
			if (popped.at(popFlag) == pushed.at(pushFlag))
			{
				++pushFlag;
				++popFlag;
			}
			else 
			{
				if (tempVec.size() <= 0)
					return false;
				else
				{
					if (popped.at(popFlag) == tempVec.top())
					{
						++popFlag;
						tempVec.pop();
					}
					else
						return false;
				}
			}
		}

		//一次性出战
		while (tempVec.size() > 0)
		{
			if (tempVec.top() != popped.at(popFlag))
				return false;
			else
			{
				tempVec.pop();
				++popFlag;
			}
		}

		return true;
	}

	//剑指 Offer 12. 矩阵中的路径
	bool dfs(vector<vector<char>>& board, int x, int y, int k, string word,int row,int col)
	{
		if (x < 0 || y < 0 || x >= row || y >= col || board.at(x).at(y) != word[k])
			return false;

		if (k == word.length() - 1)
			return true;

		board[x][y] = 0x00;

		//分四个方向查找
		bool ret =  dfs(board, x + 1, y, k + 1, word,row,col) || dfs(board, x - 1, y, k + 1, word, row, col)
			|| dfs(board, x, y + 1, k + 1, word, row, col) || dfs(board, x, y - 1, k + 1, word, row, col);
		board[x][y] = word[k];
		return ret;
	}

	bool exist(vector<vector<char>>& board, string word) {
		int row = board.size();
		int col = board.at(0).size();
		for (int i = 0; i < row; ++i)
		{
			for (int j = 0; j < col; ++j)
			{
				if (dfs(board, i, j, 0, word,row,col))
					return true;
			}
		}

		return false;
	}

	//剑指 Offer 13. 机器人的运动范围
	int val(int x, int y)
	{
		int ret = 0;
		while (x > 0)
		{
			ret += x % 10;
			x /= 10;
		}

		while (y > 0)
		{
			ret += y % 10;
			y /= 10;
		}

		return ret;
	}

	void dfsOffer13(vector<vector<int>> &matrix,int x, int y, int k)
	{
		if (x < 0 || y< 0 || x>=matrix.size() || y>= matrix.at(0).size())
			return;

		//已经走过了
		if (matrix[x][y] == 1)
			return;

		if (k < val(x, y))
			return;

		matrix[x][y] = 1;

		dfsOffer13(matrix, x + 1, y, k);
		dfsOffer13(matrix, x - 1, y, k);
		dfsOffer13(matrix, x, y + 1, k);
		dfsOffer13(matrix, x, y - 1, k);
	}

	int movingCount(int m, int n, int k) {
		vector<vector<int>> matrix(m, vector<int>(n, 0));

		int ret = 0;
		dfsOffer13(matrix, 0, 0, k);

		//统计
		for (int i = 0; i < matrix.size(); ++i)
		{
			for (int j = 0; j < matrix.at(0).size(); ++j)
			{
				if (matrix[i][j] == 1)
					++ret;
			}
		}
		
		return ret;
	}

	//剑指 Offer 15. 二进制中1的个数
	int hammingWeight(uint32_t n) {
		int ret = 0;
		for (int i = 0; i < 32; ++i)
		{
			char tt = n & 0x01;
			if (tt == 0x01)
				++ret;
			n = n >> 1;
		}
		return ret;
	}

	//剑指 Offer 16. 数值的整数次方
	double myPow(double x, int n) {

		//快速降幂
		if (n == 0)
			return 1;

		if (x == 0)
			return 0;

		long nn = n;
		bool need = n > 0 ? false : true;
		if (need)
			nn = nn * (-1);

		double ret = 1.0;
		while (nn > 0)
		{
			if (nn % 2 == 1)
				ret *= x;
			x = x * x;
			nn /= 2;
		}

		if (need)
			ret = 1.0 / ret;
		return ret;
	}

	//剑指 Offer 18. 删除链表的节点
	ListNode* deleteNode(ListNode* head, int val) {
		if (head == nullptr)
			return nullptr;

		if (head->val == val)
			head = head->next;
		else
		{
			ListNode* pTemp1 = head->next, * pTemp2 = head;
			while (pTemp1 != nullptr)
			{
				if (pTemp1->val == val)
				{
					pTemp2->next = pTemp1->next;
					break;
				}
				else
				{
					pTemp1 = pTemp1->next;
					pTemp2 = pTemp2->next;
				}
			}
		}
		

		return head;
	}

	//剑指 Offer 06. 从尾到头打印链表
	vector<int> reversePrint(ListNode* head) {
		stack<int> stackT;
		vector<int> vec;
		ListNode* tempP = head;
		while (tempP != nullptr)
		{
			stackT.push(tempP->val);
			tempP = tempP->next;
		}

		while (stackT.size() > 0)
		{
			vec.push_back(stackT.top());
			stackT.pop();
		}

		return vec;
	}

	//剑指 Offer 24. 反转链表
	ListNode* reverseList(ListNode* head)
	{
		stack<int> stackT;
		ListNode* pTemp = head;
		while (pTemp != nullptr)
		{
			stackT.push(pTemp->val);
			pTemp = pTemp->next;
		}

		pTemp = head;
		while (pTemp != nullptr)
		{
			pTemp->val = stackT.top();
			stackT.pop();
			pTemp = pTemp->next;
		}

		return head;
	}

	//剑指 Offer 35. 复杂链表的复制
	class Node {
	public:
		int val;
		Node* next;
		Node* random;

		Node(int _val) {
			val = _val;
			next = NULL;
			random = NULL;
		}
	};

	Node* MakeNode(Node* src, map<Node*, Node*>& table)
	{
		Node* ret = nullptr;
		auto it = table.find(src);
		if (it == table.end())
		{
			ret = new Node(src->val);
			table.insert(pair<Node*, Node*>(src, ret));
		}
		else
			ret = it->second;

		return ret;
	}

	Node* copyRandomList(Node* head)
	{
		if (head == nullptr)
			return nullptr;

		//记录哪些节点已经创建了
		map<Node*, Node*> cacheTable;

		Node* curNode = head;
		Node* retHead, * retTail;
		while (curNode != nullptr)
		{
			Node* tempNode = MakeNode(curNode, cacheTable);
			//处理随机指针
			if (curNode->random == nullptr)
				tempNode->random = nullptr;
			else
			{
				Node* radmNode = MakeNode(curNode->random, cacheTable);
				tempNode->random = radmNode;
			}

			if (curNode == head)
			{
				retHead = tempNode;
				retTail = retHead;
			}
			else
			{
				retTail->next = tempNode;
				retTail = retTail->next;
			}

			curNode = curNode->next;
		}

		return retHead;
	}

	//22. 括号生成

	//23. 合并K个升序链表
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		ListNode* list1 = lists.at(0);
		ListNode* list2 = nullptr;
		for (int i = 1; i < lists.size(); ++i)
		{
			list2 = lists.at(i);
			list1 = mergeTwoLists(list1, list2);
		}

		return list1;
	}

	//24. 两两交换链表中的节点
	ListNode* swapPairs(ListNode* head) {
		if (head == nullptr)
			return nullptr;

		if (head->next == nullptr)
			return head;

		ListNode* preNode = nullptr;
		ListNode* curNode = head;
		ListNode* nextNode = head->next;
		int index = 1;
		while (curNode != nullptr)
		{
			if (nextNode == nullptr)
				break;

			if (preNode == nullptr)
			{
				curNode->next = nextNode->next;
				nextNode->next = curNode;
				head = nextNode;
				preNode = curNode;
				if (curNode != nullptr)
				{
					curNode = curNode->next;
					if (curNode != nullptr)
						nextNode = curNode->next;
					else
						nextNode = nullptr;
				}
				else
				{
					curNode = nullptr;
					nextNode = nullptr;
				}
			}
			else
			{
				curNode->next = nextNode->next;
				preNode->next = nextNode;
				nextNode->next = curNode;

				preNode = curNode;
				if (curNode != nullptr)
				{
					curNode = curNode->next;
					if (curNode != nullptr)
						nextNode = curNode->next;
					else
						nextNode = nullptr;
				}
				else
				{
					curNode = nullptr;
					nextNode = nullptr;
				}

			}

		}

		return head;

	}

	//25. K 个一组翻转链表
	ListNode* reverseKGroup(ListNode* head, int k)
	{
		if (head == nullptr)
			return nullptr;

		if (k == 0 || k == 1)
			return head;
		int iCount = 1;
		bool bFirst = true;
		vector<ListNode*> vecPoint;
		ListNode* curNode = head;
		ListNode* preNode = nullptr;
		ListNode* nextNode = nullptr;
		while (curNode != nullptr)
		{
			if (iCount <= k)
			{
				vecPoint.push_back(curNode);
				curNode = curNode->next;
				++iCount;
			}
			else
			{
				iCount = 1;

				//处理翻转
				for (int i = 0; i < vecPoint.size(); ++i)
				{
					if (i == 0)
						vecPoint.at(i)->next = vecPoint.at(k - 1)->next;
					else
					{
						vecPoint.at(i)->next = vecPoint.at(i - 1);
					}
				}
				if (preNode != nullptr)
					preNode->next = vecPoint.at(k - 1);
				
				preNode = vecPoint.at(0);

				if (bFirst)
				{
					bFirst = false;
					head = vecPoint.at(k - 1);
				}
			
				vecPoint.clear();
			}
		}

		if (vecPoint.size() == k)
		{
			for (int i = 0; i < vecPoint.size(); ++i)
			{
				if (i == 0)
					vecPoint.at(i)->next = vecPoint.at(k - 1)->next;
				else
					vecPoint.at(i)->next = vecPoint.at(i - 1);
			}
			if (preNode != nullptr)
				preNode->next = vecPoint.at(k - 1);

			preNode = vecPoint.at(0);

			if (bFirst)
			{
				bFirst = false;
				head = vecPoint.at(k - 1);
			}

			vecPoint.clear();
		}

		return head;
	}

	//26 
	int removeElement(vector<int>& nums, int val) {
		vector<int>::iterator it = nums.begin();
		for (; it != nums.end();)
		{
			if (*it == val)
				it = nums.erase(it);
			else
				++it;
		}

		return nums.size();

	}

	//28. 实现 strStr()
	int strStr(string haystack, string needle) {
		int retPos = -1;
		if (needle.length() == 0)
			return 0;
		int s1 = haystack.length();
		int s2 = needle.length();
		if (s1 < s2)
			return -1;
		for (int i = 0; i <= s1 - s2; ++i)
		{
			if (haystack[i] == needle[0])
			{
				bool bOK = true;
				for (int j = 1; j < s2; ++j)
				{
					if (haystack[i + j] != needle[j])
					{
						bOK = false;
						break;
					}
				}

				if (bOK)
					retPos = i;
			}
		}
		return retPos;
	}

	//29. 两数相除
	int divide(int dividend, int divisor) {
		int INI_MIN = (-1) * pow(2, 31);

		if (dividend == 0)
			return 0;

		if (dividend == INI_MIN) {
			if (divisor == INI_MIN)
				return 1;

			if (divisor == -1)
				return INI_MIN;
		}

		if (divisor == INI_MIN)
		{
			if (dividend == INI_MIN)
				return 1;
			else
				return 0;
		}

		bool changeFlag = false;
		if (dividend > 0)
		{
			dividend = dividend * (-1);
			changeFlag *= -1;
		}

		if (divisor > 0)
		{
			divisor *= (-1);
			changeFlag *= (-1);
		}


		return 0;



	}

	//31.下一个排列，字典序排列
	void nextPermutation(vector<int>& nums) {
		int pos1 = -1,pos2 = -1;
		bool bFirst = true;
		for (int i = nums.size()-1;i > 0; --i)
		{
			if (nums.at(i) > nums.at(i - 1))
			{
				pos1 = i-1;
				break;
			}
		}

		if (pos1 == -1)
		{
			//翻转排序
			int pos1 = 0, pos2 = nums.size()-1;
			while (pos1 < pos2)
			{
				int iTemp = nums.at(pos1);
				nums.at(pos1) = nums.at(pos2);
				nums.at(pos2) = iTemp;
				++pos1;
				--pos2;
			}

			return;
		}

		for (int i = nums.size() - 1; i > pos1; --i)
		{
			if (nums.at(i) > nums.at(pos1))
			{
				pos2 = i;
				break;
			}
		}

		int tempI = nums.at(pos1);
		nums.at(pos1) = nums.at(pos2);
		nums.at(pos2) = tempI;

		for (int i = pos1 + 1; i < nums.size()-1; ++i)
		{
			for (int j = i + 1; j < nums.size(); ++j)
			{
				if (nums.at(j) < nums.at(i))
				{
					tempI = nums.at(j);
					nums.at(j) = nums.at(i);
					nums.at(i) = tempI;
				}
			}
		}
	}

	//33. 搜索旋转排序数组
	int search(vector<int>& nums, int target)
	{
		int n = (int)nums.size();
		if (!n) {
			return -1;
		}
		if (n == 1) {
			return nums[0] == target ? 0 : -1;
		}
		int l = 0, r = n - 1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (nums[mid] == target) return mid;
			if (nums[0] <= nums[mid]) {
				if (nums[0] <= target && target < nums[mid]) {
					r = mid - 1;
				}
				else {
					l = mid + 1;
				}
			}
			else {
				if (nums[mid] < target && target <= nums[n - 1]) {
					l = mid + 1;
				}
				else {
					r = mid - 1;
				}
			}
		}
		return -1;
	}

	//34. 在排序数组中查找元素的第一个和最后一个位置
	vector<int> searchRange(vector<int>& nums, int target)
	{
		if (nums.size() == 0)
			return vector<int>{-1, -1};
		if (nums.size() == 1)
		{
			if (nums.at(0) == target)
				return vector<int>{0, 0};
			else
				return vector<int>{-1, -1};
		}
		int pos = Find::Find2(nums, target);

		if (pos == -1)
			return vector<int>{-1, -1};

		vector<int> ret;
		//寻找左边界
		int posL = pos;
		while (posL >= 1)
		{
			if (nums.at(posL - 1) != nums.at(posL))
				break;
			--posL;
		}
		ret.push_back(posL);

		//寻找右边界
		int posR = pos;
		while (posR <= nums.size() - 2)
		{
			if (nums.at(posR+1) != nums.at(posR))
				break;
			++posR;
		}
		ret.push_back(posR);
		
		return ret;
	}

	//36. 有效的数独
	bool isValidSudoku(vector<vector<char>>& board)
	{
		vector<set<char>> rowSet(9, set<char>{'.'}), colSet(9, set<char>{'.'}), rcSet(9, set<char>{'.'});
		int row = board.size();
		int col = board.at(0).size();

		for (int i = 0; i < row; ++i)
		{
			for (int j = 0; j < col; ++j)
			{
				char curC = board.at(i).at(j);
				if (curC == '.')
					continue;


				//行
				if (rowSet.at(i).find(curC) != rowSet.at(i).end())
					return false;
				else
					rowSet.at(i).insert(curC);
				
				//列
				if(colSet.at(j).find(curC) != colSet.at(j).end())
					return false;
				else
					colSet.at(j).insert(curC);

				//3*3
				int k = 0;
				if(i>=0 && i<3)
				{
					if(j >= 0 && j < 3)
						k = 0;
					else if(j >=3 && j < 6)
						k = 1;
					else
						k = 2;
				}
				else if(i >= 3 && i< 6)
				{
					if(j >= 0 && j < 3)
						k = 3;
					else if(j >=3 && j < 6)
						k = 4;
					else
						k = 5;
				}
				else
				{
					if(j >= 0 && j < 3)
						k = 6;
					else if(j >=3 && j < 6)
						k = 7;
					else
						k = 8;
				}

				if(rcSet.at(k).find(curC) != rcSet.at(k).end())
					return false;
				else
					rcSet.at(k).insert(curC);
								
			}
		}

		return true;
	}

	//299. 猜数字游戏
	string getHint(string secret, string guess) {
		int sizeA = 0, sizeB = 0;
		vector<char> vecG;
		unordered_multiset<char> setS;
		int len = secret.length();
		for (int i = 0; i < len; ++i)
		{
			if (secret[i] == guess[i])
				++sizeA;
			else
			{
				setS.insert(secret[i]);
				vecG.push_back(guess[i]);
			}
		}

		for (auto it : vecG)
		{
			if (setS.size() <= 0)
				break;
			else
			{
				if (setS.find(it) != setS.end())
				{
					++sizeB;
					setS.erase(setS.find(it));
				}
					
			}
		}

		char charTemp[10] = { 0x00 };
		sprintf(charTemp, "%dA%dB", sizeA, sizeB);
		return charTemp;
	}

	//55. 跳跃游戏
	bool canJump1(vector<int>& nums, int target_index)
	{
		int len = target_index;
		vector<bool> vec;
		for (int i = 0; i <= target_index - 1; ++i)
		{
			if (nums.at(i) >= (target_index - i))
				vec.push_back(true);
			else
				vec.push_back(false);
		}

		if (vec.at(0) == true)
			return true;

		bool bRet = false;
		for (int i = 0; i < vec.size(); ++i)
		{
			if (vec.at(i) == false)
				continue;
			else
			{
				if (canJump1(nums, i))
					return true;
			}
		}

		return false;
	}

	bool canJump(vector<int>& nums) {
		//递归，超时
		//return canJump1(nums, nums.size() - 1);
		bool bRet = false;
		int maxStep = 0;
		for (int i = 0; i < nums.size(); ++i)
		{
			if (i > maxStep)
				break;

			if (maxStep < (nums.at(i) + i))
				maxStep = nums.at(i) + i;

			if (maxStep >= nums.size() - 1)
			{
				bRet = true;
				break;
			}
		}

		return bRet;
	}

	//1299. 将每个元素替换为右侧最大元素
	vector<int> replaceElements(vector<int>& arr) {
		stack<int> flag;
		for (int i = arr.size() - 1; i >= 0; --i)
		{
			if (flag.empty())
				flag.push(arr.at(i));
			else
			{
				if (flag.top() < arr.at(i))
					flag.push(arr.at(i));
			}
		}

		for (int i = 0; i < arr.size() - 1; ++i)
		{
			if (arr.at(i) == flag.top())
				flag.pop();

			arr.at(i) = flag.top();
		}

		arr.at(arr.size() - 1) = -1;

		return arr;
	}

	//面试题 04.05.合法二叉搜索树
	bool isValidBST1(TreeNode* root,long long lower,long long  upper)
	{
		if (root == nullptr)
			return true;

		if (root->val <= lower || root->val >= upper)
			return false;

		return isValidBST1(root->left, lower, root->val) || isValidBST1(root->right, root->val, upper);
	}

	bool isValidBST(TreeNode* root) {

		vector<int> valList;
		//中序遍历
		stack<TreeNode*> stack;
		while (!stack.empty() || root != nullptr)
		{
			//先找到最左边的节点
			while (root != nullptr)
			{
				stack.push(root);
				root = root->left;
			}

			root = stack.top();
			stack.pop();

			valList.push_back(root->val);
			root = root->right;
		}

		for (int i = 0; i < valList.size()-1; ++i)
		{
			if (valList.at(i) >= valList.at(i + 1))
				return false;
		}

		return true;

	}

	namespace Day20211220
	{
		//56. 合并区间
		vector<vector<int>> merge(vector<vector<int>>& intervals) {
			vector<vector<int>> vecRet;

			//排序
			for (int i = 0; i < intervals.size(); ++i)
			{
				for (int j = i + 1; j < intervals.size(); ++j)
				{
					if (intervals.at(i).at(0) > intervals.at(j).at(0))
					{
						int m = intervals.at(i).at(0);
						int n = intervals.at(i).at(1);

						intervals.at(i).at(0) = intervals.at(j).at(0);
						intervals.at(i).at(1) = intervals.at(j).at(1);

						intervals.at(j).at(0) = m;
						intervals.at(j).at(1) = n;
					}
				}
			}

			//再合并
			for (int i = 0; i < intervals.size(); ++i)
			{
				if (vecRet.size() == 0)
					vecRet.push_back(intervals.at(i));
				else
				{
					if (intervals.at(i).at(0) > vecRet.at(vecRet.size() - 1).at(1))
						vecRet.push_back(intervals.at(i));
					else
					{
						vecRet.at(vecRet.size() - 1).at(1) = intervals.at(i).at(1) > vecRet.at(vecRet.size() - 1).at(1)?intervals.at(i).at(1) : vecRet.at(vecRet.size() - 1).at(1);
					}
				}
			}

			return vecRet;
		}

		//57. 插入区间
		vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {

			if (intervals.size() == 0)
				return vector<vector<int>>{newInterval};

			vector<vector<int>> temp;

			bool isInsert = false;
			//先按左端点排序
			for (int i = 0; i < intervals.size(); ++i)
			{
				if (isInsert)
					temp.push_back(intervals.at(i));
				else
				{
					if (intervals.at(i).at(0) <= newInterval.at(0))
						temp.push_back(intervals.at(i));
					else
					{
						temp.push_back(newInterval);
						isInsert = true;
					}
				}
			}
			//再合并区间
			vector<vector<int>> ret = merge(temp);
			return ret;
		}

		//475.供暖器
		int findRadius(vector<int>& houses, vector<int>& heaters) {
			return 1;
		}

		//剑指 Offer 03. 数组中重复的数字
		int findRepeatNumber(vector<int>& nums) {
			set<int> setV;
			for (int i = 0; i < nums.size(); ++i)
			{
				if (setV.find(nums.at(i)) != setV.end())
					return nums.at(i);
				else
					setV.insert(nums.at(i));
			}

			return -1;
		}

		//剑指 Offer 53 - I.在排序数组中查找数字 I
		int search(vector<int>& nums, int target) {

			int sizeT = nums.size();
			if (target < nums.at(0))
				return 0;

			if (target > nums.at(sizeT-1))
				return 0;

			int count = 0;
			for (int i = 0; i < sizeT; ++i)
			{
				if (target > nums.at(i))
					continue;
				else if (target == nums.at(i))
					++count;
				else
					break;
			}

			return count;
		}

		//剑指 Offer 53 - II. 0～n-1中缺失的数字
		int missingNumber(vector<int>& nums) {
			//方案1：遍历
			int sizeT = nums.size();
			for (int i = 0; i < sizeT; ++i)
			{
				if (nums.at(i) != i)
					return i;
			}

			return sizeT;
		}

		//剑指 Offer 04. 二维数组中的查找
		bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
			return true;
		}

		//剑指 Offer 11. 旋转数组的最小数字
		int minArray(vector<int>& numbers) {
			if (numbers.size() == 0)
				return 0;
			if (numbers.size() == 1)
				return numbers.at(0);

			int size = numbers.size();
			int l = 0, r = numbers.size() - 1;
			while (l < r)
			{
				int mid = l + (r - l) / 2;
				if (numbers.at(mid) < numbers.at(size - 1))
					r = mid;
				else if (numbers.at(mid) > numbers.at(size - 1))
					l = mid;
				else
					r -= 1;
			}

			return numbers.at(l);
		}

		//剑指 Offer 50. 第一个只出现一次的字符
		char firstUniqChar(string s) {
			array<vector<int>, 26> arrayList;
			for (int i = 0; i < s.length(); ++i)
				arrayList[s[i] - 'a'].push_back(i);

			char charC = ' ';
			int pos = -1;
			for (int i = 0; i < 26; ++i)
			{
				if (arrayList[i].size() == 1)
				{
					if (pos == -1)
					{
						charC = s[arrayList[i].at(0)];
						pos = arrayList[i].at(0);
					}
					else 
					{
						if (arrayList[i].at(0) < pos)
						{
							charC = s[arrayList[i].at(0)];
							pos = arrayList[i].at(0);
						}
					}
				}
			}

			return charC;
		}

		//剑指 Offer 32 - I. 从上到下打印二叉树
		vector<int> levelOrder(TreeNode* root) {
			vector<int> ret;
			if (root == nullptr)
				return ret;

			list<TreeNode*> list;
			list.push_back(root);
			while (list.size() > 0)
			{
				TreeNode* point = list.front();
				if (point->left != nullptr)
					list.push_back(point->left);
				
				if (point->left != nullptr)
					list.push_back(point->right);

				ret.push_back(point->val);
				list.pop_front();
			}

			return ret;

		}

		//剑指 Offer 32 - II. 从上到下打印二叉树 II
		vector<vector<int>> levelOrder2(TreeNode* root)
		{
			vector<vector<int>> ret;
			if (root == nullptr)
				return ret;

			vector<vector<TreeNode*>> tempV;
			vector<TreeNode*> tt{ root };
			tempV.push_back(tt);
			int lastSize = 0;
			while (true)
			{
				int size = tempV.size()-1;
				vector<TreeNode*> temp;
				for (int i = 0; i < tempV.at(size).size(); ++i)
				{
					if (tempV.at(size).at(i)->left != nullptr)
						temp.push_back(tempV.at(size).at(i)->left);

					if (tempV.at(size).at(i)->right != nullptr)
						temp.push_back(tempV.at(size).at(i)->right);
				}

				if (temp.size() > 0)
					tempV.push_back(temp);
				else
					break;
			}

			for (int i = 0; i < tempV.size(); ++i)
			{
				vector<int> tempRet;
				for (int j = 0; j < tempV.at(i).size(); ++j)
					tempRet.push_back(tempV.at(i).at(j)->val);
				ret.push_back(tempRet);
			}

			return ret;
		}

		//剑指 Offer 32 - III.从上到下打印二叉树 III
		vector<vector<int>> levelOrder3(TreeNode* root) {
			vector<vector<int>> ret;
			if (root == nullptr)
				return ret;

			vector<vector<TreeNode*>> tempV;
			vector<TreeNode*> tt{ root };
			tempV.push_back(tt);
			int lastSize = 0;
			while (true)
			{
				int size = tempV.size() - 1;
				vector<TreeNode*> temp;
				for (int i = 0; i < tempV.at(size).size(); ++i)
				{
					if (tempV.at(size).at(i)->left != nullptr)
						temp.push_back(tempV.at(size).at(i)->left);

					if (tempV.at(size).at(i)->right != nullptr)
						temp.push_back(tempV.at(size).at(i)->right);
				}

				if (temp.size() > 0)
					tempV.push_back(temp);
				else
					break;
			}

			for (int i = 0; i < tempV.size(); ++i)
			{
				vector<int> tempRet;
				if (i % 2 == 0)
				{
					for (int j = 0; j < tempV.at(i).size(); ++j)
						tempRet.push_back(tempV.at(i).at(j)->val);
				}
				else
				{
					for (int j = tempV.at(i).size()-1; j >= 0 ; --j)
						tempRet.push_back(tempV.at(i).at(j)->val);
				}
				
				ret.push_back(tempRet);
			}

			return ret;
		}

		//50.Pow(x, n)
		double myPow(double x, int n) {
			//快速降幂

			if (x == 0)
				return 0;
			if (n == 0)
				return 1;

			double ret = 1.0;
			while (n != 1 && n != -1)
			{
				if (n % 2 == 0)
					ret *= 1.0;
				else
					ret *= x;
				n = n / 2;
				x = x * x;
			}

			if(n == 1)
				return ret * x;

			return 1 / (ret * x);

		}

		//54. 螺旋矩阵
		vector<int> spiralOrder(vector<vector<int>>& matrix)
		{
			if (matrix.size() == 0 || matrix.at(0).size() == 0)
				return vector<int>{};

			int rows = matrix.size();
			int col = matrix.at(0).size();
			vector<int> ret;

			int top = 0, left = 0, right = col - 1, bottom = rows - 1;
			while (left <= right && top <= bottom)
			{
				for (int i = left; i <= right; ++i)
					ret.push_back(matrix[top][i]);

				for (int i = top + 1; i <= bottom; ++i)
					ret.push_back(matrix[i][right]);

				if (left < right && top < bottom)
				{
					for (int i = right - 1; i >= left; --i)
						ret.push_back(matrix[bottom][i]);

					for (int i = bottom - 1; i > top; --i)
						ret.push_back(matrix[i][left]);
				}

				++top;
				++left;
				--right;
				--bottom;
			}

			return ret;
			
		}
	}*/

}	

